package linkedList;

/**
 * 删除链表的倒数第 N 个结点 -21
 *
 * @author yyz
 * @create 2023-11-21 16:12
 */
public class 删除链表的倒数第N个结点 {
    /**
     * 删除链表倒数第N个节点(方法1)
     * @param head 链表的头节点
     * @param n 要删除的节点的位置（倒数第n个）
     * @return 删除节点后的链表头节点
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个虚拟头节点s，值为-1，指向head
        ListNode s = new ListNode(-1, head);
        // 递归删除倒数第n个节点
        recursion(s, n);
        // 返回虚拟头节点s的next指针，即删除节点后的链表头节点
        return s.next;
    }
    /**
     * 删除链表倒数第N个节点(方法2)
     * @param head 链表的头节点
     * @param n 要删除的节点的位置（倒数第n个）
     * @return 删除节点后的链表头节点
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        // 创建一个虚拟头节点s，值为-1，指向head
        ListNode s = new ListNode(-1, head);
        // 创建两个指针p1和p2，初始都指向虚拟头节点s
        ListNode p1 = s;
        ListNode p2 = s;
        // 将p2向前移动n+1个节点
        for (int i = 0; i < n + 1; i++) {
            p2 = p2.next;
        }
        // 同时将p1和p2向前移动，直到p2到达链表末尾
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 此时p1指向要删除节点的前一个节点，删除p1.next节点
        p1.next = p1.next.next;
        // 返回虚拟头节点s的next指针，即删除节点后的链表头节点
        return s.next;
    }

    /**
     * 递归删除倒数第N个节点
     * @param p 当前节点
     * @param n 要删除的节点的位置（倒数第n个）
     * @return 当前节点到链表末尾的节点数
     */
    private static int recursion(ListNode p, int n) {
        // 如果当前节点为空，返回0
        if (p == null) {
            return 0;
        }
        // 递归删除下一个节点
        int endNum = recursion(p.next, n);
        // 如果当前节点到链表末尾的距离为n，则删除下一个节点
        if (endNum == n) {
            p.next = p.next.next;
        }
        // 返回当前节点到链表末尾的距离+1
        return endNum + 1;
    }


    public static void main(String[] args) {
        ListNode list = ListNode.of(1, 2, 3, 4, 5);
        System.out.println(removeNthFromEnd2(list, 5));
    }
}
